package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author shiminghui
 * @date 2025/3/16 10:25
 * @description: TODO
 */
public class _051_HuffmanTree {

    @Test
    public void test() {
        String s = new String("abcccccccccccddd");
        HuffmanTree huffmanTree = new HuffmanTree(s);
        String encode = huffmanTree.encode();
        System.out.println(encode);
        String parse = huffmanTree.parse(encode);
        System.out.println(parse);
    }

    private static class HuffmanTree {
        private String str;
        private Node root;
        private HashMap<Character, Node> map;

        public HuffmanTree(String str) {
            this.str = str;
            createTree(str);
        }

        public String parse(String str) {
            char[] charArray = str.toCharArray();
            int index = 0;
            StringBuffer sb = new StringBuffer();
//            StringBuffer tempSb = new StringBuffer();
            while (index < str.length()) {
                Node cur = root;

                while (!cur.isLeaf()) {
                    if (charArray[index] == '0') {
                        cur = cur.left;
                    } else {
                        cur = cur.right;
                    }
                    index++;
                }
                sb.append(cur.ch);

            }
            return sb.toString();
        }


        /**
         * 编码
         *
         * @return
         */
        public String encode() {
            char[] charArray = str.toCharArray();
            StringBuffer sb = new StringBuffer();
            for (char aChar : charArray) {
                Node node = map.get(aChar);
                sb.append(node.code);
            }
            return sb.toString();
        }


        // 建树
        private void createTree(String str) {
            // 先统计数的频次
            char[] chars = str.toCharArray();
            map = new HashMap<>();
            for (char aChar : chars) {
                Node node = map.get(aChar);
                if (node != null) {
                    node.frequency++;
                } else {
                    map.put(aChar, new Node(aChar, 1));
                }
            }
            // 建立赫夫曼树
            PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(Node::getFrequency));
            minHeap.addAll(map.values());

            while (minHeap.size() > 1) {
                Node left = minHeap.poll();
                Node right = minHeap.poll();
                Node parent = new Node(null, left.frequency + right.frequency, left, right);
                minHeap.add(parent);
            }
            Node root = minHeap.poll();
            this.root = root;
            printTree(root, new StringBuilder());
        }

        private void printTree(Node root, StringBuilder sb) {
            if (root == null || root.isLeaf()) {
//                System.out.println(root.ch==null ? "null" : root.ch + sb.toString());
                root.code = sb.toString();
                sb.deleteCharAt(sb.length() - 1);
                return;
            }
            sb.append('0');
            printTree(root.left, sb);

            sb.append('1');
            printTree(root.right, sb);

            if (!sb.isEmpty()) {
                sb.deleteCharAt(sb.length() - 1);
            }
        }

        private static class Node {
            private Character ch;
            private int frequency; // 节点频次
            private String code; // 节点编码
            private Node left;
            private Node right;

            public Node(int frequency) {
                this.frequency = frequency;
            }

            public Node(Character ch, int frequency) {
                this.ch = ch;
                this.frequency = frequency;
            }

            public Node(Character ch, int frequency, Node left, Node right) {
                this.frequency = frequency;
                this.left = left;
                this.right = right;
            }

            public boolean isLeaf() {
                return left == null && right == null;
            }

            public int getFrequency() {
                return frequency;
            }

            public void setFrequency(int frequency) {
                this.frequency = frequency;
            }

            public Node getLeft() {
                return left;
            }

            public void setLeft(Node left) {
                this.left = left;
            }

            public Node getRight() {
                return right;
            }

            public void setRight(Node right) {
                this.right = right;
            }
        }

    }


}
